Section: New Results

Exhaustive Family of Energies Minimizable Exactly by a Graph Cut

Participant : Guillaume Charpiat.

Graph cuts are widely used in many fields of computer vision in order to minimize in small polynomial time complexity certain classes of energies. These specific classes depend on the way chosen to build the graphs representing the problems to solve. We study here all possible ways of building graphs and the associated energies minimized, leading to the exhaustive family of energies minimizable exactly by a graph cut. To do this, we consider the issue of coding pixel labels as states of the graph, i.e. the choice of state interpretations. The family obtained comprises many new classes, in particular energies that do not satisfy the submodularity condition, including energies that are even not permuted-submodular.

We studied in details a generating subfamily, in particular we proposed a canonical form to represent Markov random fields, which proves useful to recognize energies in this subfamily in linear complexity almost surely, and then to build the associated graph in quasilinear time. We performed a few experiments to illustrate the new possibilities offered [33] . We have also started to use this technique to minimize exactly approximations of Markov random field energies instead of minimizing approximately the exact energies, by projecting energies on the family we know to solve globally efficiently.